package com.cet.algorithm.test.数组;

/**
 * @program: cet-practice
 * @description: 数组中第K大元素
 * @author: 陈恩涛
 * @create: 2023-05-14 16:49
 **/
public class LC215 {

    /**
     * 寻找数组中第k大的数
     * 快排中，每次partition操作返回的即为pivot的最终位置下标
     * @param nums 无序数组
     * @param k 目标数的大小次序
     * @return 第k大元素
     */
    public int findKthLargest(int[] nums, int k) {

        int start = 0;
        int end = nums.length - 1;

        int targetIndex = nums.length - k;

        while (true) {
            int pivotIndex = partition(nums, start, end);
            if (pivotIndex == targetIndex) {
                return nums[pivotIndex];
            } else if (pivotIndex > targetIndex) {
                end = pivotIndex - 1;
            } else {
                start = pivotIndex + 1;
            }
        }
    }

    /**
     * 对数组 nums 的子区间 [left..right] 执行 partition 操作，返回 nums[left] 排序以后应该在的位置
     * 在遍历过程中保持循环不变量的定义：
     * nums[left + 1..j] < nums[left]
     * nums(j..i) >= nums[left]
     *
     * @param nums 无序数组
     * @param left 开始下标
     * @param right 结束下标
     * @return pivot排序后的位置
     */
    public int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                j++;
                swap(nums, j, i);
            }
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

class ClientQS{
    public static void main(String[] args) {
        LC215 lc215 = new LC215();
        int[] nums = {3, 1, 5, 4, 2, 3, 4, 5, 5};
        System.out.println(lc215.findKthLargest(nums, 8));
    }
}
